package leetcode_1000;

import java.util.Arrays;

/**
 *@author 周杨
 *SmallestRangeII_910_ 一个数组里每个元素要么+K 要么-k 问最后数组里最大值和最小值的差值 最小是多少
 *describe:先对数组排序 然后选择反转点 AC 45%
 *2018年11月16日 下午9:01:39
 */
public class SmallestRangeII_910_ {
	public int smallestRangeII(int[] A, int K) {
        int N = A.length;
        Arrays.sort(A);
        int ans = A[N-1] - A[0];//最差的情况无非就是所有元素+K
        int max=A[N-1]-K,min=A[0]+K;//max-k那么可能是反转后的最大值，min+k可能是反转后的最小值
        //那么我们选择任意一个位置反转这个数组 在这个位置左边全部+k 右边全部-k
        //那么这个位置就是反转后的最优解 我们只需取每一个最优解的最小值
        for (int i = 0; i < A.length - 1; ++i) {
            int a = A[i], b = A[i+1];
            int high = Math.max(max, a + K);
            int low = Math.min(min, b - K);
            ans = Math.min(ans, high - low);
        }
        return ans;
    }
}
